/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author zhong
 *
 */
public class VideoStitching {
	public int videoStitching(int[][] clips, int T) {
		Arrays.sort(clips, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] != o2[0]) {
					return o1[0] - o2[0];
				}
				return o2[1] - o1[1];
			}
		});
		int lastend = 0;
		int res = 0;
		int i = 0;
		while (lastend < T) {
			// 找start<=lastend的所有，定位到end最大的
			int maxEnd = lastend;
			for (; i < clips.length && clips[i][0] <= lastend; i++) {
				maxEnd = Math.max(maxEnd, clips[i][1]);
			}
			if (maxEnd == lastend) {
				return -1;
			}
			lastend = maxEnd;
			res++;
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] clips = { { 0, 2 }, { 4, 6 }, { 8, 10 }, { 1, 9 }, { 1, 5 }, { 5, 9 } };
		int T = 10;
		System.out.println(new VideoStitching().videoStitching(clips, T));
	}

}
